home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1999 June: Reference Library / Dev.CD Jun 99 RL Disk 1.toast / Technical Documentation / Develop / develop Issue 26 / develop Issue 26 code / Truffles - Display Mgr. / Sprocket / Sources / SortedDynamicArray.cp < prev    next >
Encoding:
Text File  |  1995-01-03  |  1.3 KB  |  71 lines  |  [TEXT/MMCC]
  1. /*
  2.     File:        SortedDynamicArray.cp
  3.  
  4.     Contains:    An abstract base class for sorted dynamic arrays
  5.                 
  6.     Written by: Dave Falkenburg
  7.     
  8.     Copyright:    © 1994-95 by Dave Falkenburg, all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.      
  12.          <1>      1/3/95    DRF        First checked in.
  13.  */
  14.  
  15. #include    "SortedDynamicArray.h"
  16.  
  17. TSortedDynamicArray::TSortedDynamicArray()
  18.     {
  19.     }
  20.  
  21.  
  22. //    TSortedDynamicArray::Add
  23. //
  24. //    An O(n) (insertion sort) routine for adding elements
  25.  
  26. OSErr
  27. TSortedDynamicArray::Add(ArrayElementPtr newElement)
  28.     {
  29.     ArrayElementIndex    index;
  30.  
  31.     for (index = 0;index < fElementCount;index++)
  32.         {
  33.         if (this->Compare(newElement,(*fStorage)[index]) > 0)
  34.             continue;
  35.  
  36.         return this->Insert(newElement,index);
  37.         }
  38.  
  39.     return this->InsertLast(newElement);
  40.     }
  41.  
  42.  
  43. //    TSortedDynamicArray::Find
  44. //
  45. //    A O(lg n) (binary search) routine for finding elements
  46.  
  47. ArrayElementPtr
  48. TSortedDynamicArray::Find(ArrayElementPtr prototypeElement)
  49.     {
  50.     ArrayElementIndex    low,high,index;
  51.     long                value;
  52.     
  53.     low = 0;
  54.     high = fElementCount;
  55.     
  56.     while (low < high)
  57.         {
  58.         index = (low+high)/2;
  59.         value = this->Compare(prototypeElement,(*fStorage)[index]);
  60.         
  61.         if (value < 0)
  62.             high = index;                    //    element is below "high"
  63.         else if (value == 0)
  64.             return (*fStorage)[index];        //    found the element
  65.         else
  66.             low = index+1;                    //    element is above "low"
  67.         }
  68.  
  69.     return NULL;
  70.     }
  71.